package com.feiyue.learning.sort;

import java.util.Arrays;

/**
 * 希尔排序
 * @author  feiyue
 * @date  2020/3/29
 */
public class ShellSort {

    public static void main(String[] args) {

        int[] data = new int[]{1, 3, 5, 4, 7, 6, 2};

        System.out.print("排序前: ");
        Arrays.stream(data).forEach(r->System.out.print(r + " "));

        shellSort(data);

        System.out.print("排序后: ");
        Arrays.stream(data).forEach(r->System.out.print(r + " "));
    }

    private static void shellSort(int[] data) {

        // 初始间隔
        int jump = 1;
        while (jump < data.length / 3) {
            jump = jump * 3 + 1;
        }
        System.out.println("\nshell jump = " + jump);

        // 每个间隔均进行一次排序, 直至间隔为 1 排完
        while (jump >= 1) {
            for (int i = jump; i < data.length; i++) {

                // 当前要排序的数据
                int temp = data[i];

                // 当前数据的上一个数据索引
                int k = i - jump;

                // 插入排序
                while (k >= 0 && temp < data[k]) {
                    data[k + jump] = data[k];
                    k -= jump;
                }
                data[k + jump] = temp;
            }

            jump = jump / 3;
        }
    }
}
